import java.util.Scanner;

/**
 * @author gao
 * @date 2025/6/10 15:18
 */

public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;

        // 创建一个二维数组dp，用于存储到达每个位置的最小路径和
        int[][] dp = new int[n + 1][n + 2];

        // 将dp的第一行和最后一行初始化为最大值，表示无法到达这些位置
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 计算到达当前位置的最小路径和
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }

        // 初始化最小路径和为最大值
        int ret = Integer.MAX_VALUE;
        // 遍历dp的最后一行，找到最小路径和
        for (int i = 1; i <= n; i++) {
            ret = Math.min(ret, dp[n][i]);
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[][] matrix = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = in.nextInt();
                }
            }
            Solution solution = new Solution();
            System.out.println(solution.minFallingPathSum(matrix));
        }
    }
}